Vào ngày 17 tháng 5 năm 2007, Tony Fernandes đã công bố kế hoạch bắt đầu các chuyến bay từ Malaysia đến Úc. Fernandes cho biết ông sẽ tránh sân bay Sydney do mức phí cao. Thay vào đó, hãng sẽ tập trung vào các lựa chọn thay thế rẻ hơn như sân bay Avalon của Melbourne, sân bay Williamtown ở Newcastle và sân bay Adelaide. Giá vé duy trì được dự đoán là khoảng 800 MYR (285 đô la Úc) cho giá vé khứ hồi, cộng với thuế. Sự quan tâm cũng được thể hiện khi sử dụng Sân bay Gold Coast làm điểm đến khác của Úc. Một số phát triển lớn đã được công bố vào ngày 10 tháng 8 năm 2007, AirAsia X đã công bố tuyến bay đầu tiên từ Kuala Lumpur đến Gold Coast, với giá vé một chiều bắt đầu từ 50 MYR (17 đô la Úc) không bao gồm thuế và phí, với giá vé trung bình là khoảng MYR 1 800 (598 đô la Úc), đã bao gồm thuế và phí.

Hãng hàng không cũng thông báo rằng ông Richard Branson thuộc Tập đoàn Virgin, sẽ lấy 20% cổ phần của hãng hàng không để giúp bắt đầu các hoạt động đường dài và tài trợ cho việc mua máy bay của họ. Branson cũng dự báo khả năng mạnh mẽ trong tương lai, các liên kết chính thức giữa Virgin Blue và AirAsia X, bao gồm các thỏa thuận liên danh và chương trình Loyalty.[3][4]

Máy bay AirAsia X đầu tiên đã đến Sân bay Quốc tế Kuala Lumpur vào ngày 15 tháng 9 năm 2007. Hãng được đặt tên là "Semangat Sir Freddie" (tiếng Anh: "Spirit of Sir Freddie") theo tên của người tiên phong và người sáng lập mô hình giá rẻ; người quá cố, Ngài Freddie Laker của Skytrain.